package com.heima.leetcode.practice;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 95. 不同的二叉搜索树 II
 * @date 2025/5/20 10:27
 */
public class E95 {

    // 卡特兰数
    public List<TreeNode> generateTrees(int n) {
        List<TreeNode> result = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            List<TreeNode> leftRoots = generateTrees(1, i - 1);
            List<TreeNode> rightRoots = generateTrees(i + 1, n);
            for (TreeNode leftRoot : leftRoots) {
                for (TreeNode rightRoot : rightRoots) {
                    TreeNode root = new TreeNode(i);
                    root.left = leftRoot;
                    root.right = rightRoot;
                    result.add(root);
                }
            }
        }
        return result;
    }

    private List<TreeNode> generateTrees(int start, int end) {
        List<TreeNode> result = new ArrayList<>();
        if (end < start) {
            result.add(null);
            return result;
        }
        if (end == start) {
            result.add(new TreeNode(start));
            return result;
        }
        for (int i = start; i <= end; i++) {
            List<TreeNode> leftRoots = generateTrees(start, i - 1);
            List<TreeNode> rightRoots = generateTrees(i + 1, end);
            for (TreeNode leftRoot : leftRoots) {
                for (TreeNode rightRoot : rightRoots) {
                    TreeNode root = new TreeNode(i);
                    root.left = leftRoot;
                    root.right = rightRoot;
                    result.add(root);
                }
            }
        }
        return result;
    }
}
